package week_4;


public class MySortedLinkedList<E extends Comparable<E>>
{
	private ComparableListNode<E> head_ = null;
	
	@Override
	public String toString()
	{
		String s = "";
		
		ComparableListNode<E> current = head_;
		
		while (current != null)
		{
			s += " -> " + current.toString();
			
			current = current.next_;
		}
		
		return !s.isEmpty() ? s.substring(4) : "-empty-";
	}
	
	public void add(E data)
	{
		if (head_ == null)
		{
			head_ = new ComparableListNode<E>(data, null);
		}
		else if (head_.next_ == null)
		{
			ComparableListNode<E> newNode = new ComparableListNode<E>(data, null);
			
			// Should it come after the head?
			if (head_.data_.compareTo(newNode.data_) < 0)
			{
				// Place it after the head.
				head_.next_ = newNode;
			}
			else
			{
				// Place it before the head, so the new node will become the
				// head.
				newNode.next_ = head_;
				
				head_ = newNode;
			}
		}
		else
		{
			ComparableListNode<E> newNode = new ComparableListNode<E>(data, null);
			
			// The head.
			ComparableListNode<E> currentNode = head_;
			
			// [1], 2, 3
			// Special case, there are 2 elements, and it must become before the
			// head.
			if (currentNode.data_.compareTo(data) >= 0)
			{
				// Place it before the head, so the new node will become the
				// head.
				newNode.next_ = head_;
				
				head_ = newNode;
			}
			// 1, 2, [3], 5
			// Loop till the tail, which has no next.
			else
			{
				while (currentNode.next_ != null)
				{
					// Should it become after the next node.
					if (currentNode.next_.data_.compareTo(data) < 0)
					{
						// Check if maybe it should go after the next one.
						currentNode = currentNode.next_;
						
						if (currentNode.next_ != null)
						{
							continue;
						}
					}
					
					// 3 -> 5
					newNode.next_ = currentNode.next_;
					
					// 2 -> 3
					currentNode.next_ = newNode;
					
					break;
				}
			}
		}
	}
	
	public void delete(E data)
	{
		// The head.
		ComparableListNode<E> currentNode = head_;
		
		if (currentNode.data_.equals(data))
		{
			head_ = currentNode.next_;
			
			return;
		}
		
		while (currentNode != null && currentNode.next_ != null)
		{
			if (currentNode.next_.data_.equals(data))
			{
				currentNode.next_ = currentNode.next_.next_;
			}
			
			currentNode = currentNode.next_;
		}
	}
	
	public static void main(String[] args)
	{
		MySortedLinkedList<Integer> list = new MySortedLinkedList<Integer>();
		list.add(10);
		System.out.println(list.toString());
		list.add(200);
		System.out.println(list.toString());
		list.add(-30);
		System.out.println(list.toString());
		list.add(50);
		System.out.println(list.toString());
		list.add(-40);
		System.out.println(list.toString());
		list.add(20);
		System.out.println(list.toString());
		
		list.delete(50);
		System.out.println(list.toString());
		list.delete(200);
		System.out.println(list.toString());
		list.delete(-40);
		System.out.println(list.toString());
		list.delete(15);
		System.out.println(list.toString());
	}
}
